package HuaweiMeeting;

import java.util.*;

public class Test1 {
    /**
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
     * 请你找出所有和为 0 且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     *
     * 示例 1：
     *
     * 输入：nums = [-1,0,1,2,-1,-4]
     * 输出：[[-1,-1,2],[-1,0,1]]
     *
     * 示例 2：
     * 输入：nums = []
     * 输出：[]
     * 示例 3：
     *
     * 输入：nums = [0]
     * 输出：[]
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {-1,0,0,1,1,2,2,-1,-4};
        int[][] ints = find2(arr);
        System.out.println("------------");
    }
    public static int[][] find(int[] arr){
        if (arr.length < 3) return new int[0][];
        List<int[]> res = new ArrayList<>();
        Arrays.sort(arr);
        for (int i = 0; i < arr.length - 2; i++) {
            if (i > 0 && arr[i] == arr[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < arr.length - 1; j++) {
                if (j != i + 1 && arr[j] == arr[j - 1]){
                    continue;
                }
                for (int k = j + 1; k < arr.length; k++) {
                    if (k != j + 1 && arr[k] == arr[k - 1]) {
                        continue;
                    }
                    if (arr[i] + arr[j] + arr[k] == 0){
                        res.add(new int[]{arr[i], arr[j], arr[k]});
                    }
                }
            }
        }
        return res.toArray(new int[0][]);
    }
    public static int[][] find2(int[] arr){
        if (arr.length < 3) return new int[0][];
        List<int[]> res = new ArrayList<>();
        Arrays.sort(arr);
        Set<Integer> set = new HashSet<>();
        for (int num : arr) set.add(num);
        for (int i = 0; i < arr.length - 1; i++) {
            if (i != 0 && arr[i] == arr[i - 1]) continue;
            for (int j = i + 1; j < arr.length; j++) {
                if (j != i + 1 && arr[j] == arr[j - 1]) continue;
                if (set.contains(-(arr[i] + arr[j]))){
                    res.add(new int[]{arr[i], arr[j], -(arr[i] + arr[j])});
                }
            }
        }
        return res.toArray(new int[0][]);
    }
}
